package study.datastructure.heap;/**
 * @program: datastructure
 * @author: lcy
 * @create: 2024-11-05 19:22
 */

import java.util.Arrays;

/**
 2024/11/5,
 */


public class MinHeap {
    private int size;
    private int [] array;

    public MinHeap(int [] array){
        this.array=array;
        this.size=array.length;
        heapify();
    }
    public MinHeap(int capacity){
        array=new int[capacity];
        size=0;
    }
    public void heapify(){
        for(int i=size/2-1;i>=0;i--){
            down(i);
        }
    }

    /**
     * 增加元素
     * @param inserted
     * @return 是否成功
     */
    public boolean offer(int inserted){
        if (size==array.length){
            return false;
        }
        //添加到数组尾部
        array[size++]=inserted;

        //添加元素 上浮到顶
        up(size-1);
        return true;
    }

    /**
     * 获取最大值
     * @return
     */
    public int getMax(){
        return array[0];
    }

    /**
     * 替换堆顶元素
     * @param value
     */
    public void replace(int value){
        array[0]=value;
        down(0);
    }

    /**
     * 修改元素
     * @param index
     * @param value
     */
    public void update(int index,int value){
        array[index]=value;
        if (array[index]>array[(index-1)/2]){
            up(index);
        }else {
            down(index);
        }
    }



    /**
     * 取出堆顶元素
     * @return
     */
    public int poll(){
        int max=array[0];
        //移除堆顶元素
        array[0]=array[--size];
        down(0);
        return max;
    }


    private void up(int index){
        //找到父节点
        int parent=(index-1)/2;

        //交换值
        if(parent>=0&&array[parent]>array[index]){
            swap(parent,index);
            up(parent);
        }
    }



    /**
     * 下潜  跟所有 相关的孩子 交换 往下潜
     * @param i
     */
    private void down(int i){
        int left=2*i+1;
        int right=left+1;

        int min=i;

        if (left<size&&array[left]<array[min]){
            min=left;
        }
        if (right <size&&array[right]<array[min]){
            min=right;
        }
        if(min!=i){
            swap(i,min);
            down(min);
        }
    }

    private void swap(int i,int j){
        int t=array[i];
        array[i]=array[j];
        array[j]=t;
    }

    public boolean isFull(){return size==array.length;}

    public int peek(){return array[0];}

    @Override
    public String toString() {
        return "MaxHeap{" +
                "array=" + Arrays.toString(array) +
                '}';
    }


    public static void main(String[] args) {
        // 初始化一个数组并创建一个最小堆
        int[] initialArray = {5, 3, 8, 4, 1, 2};
        MinHeap minHeap = new MinHeap(initialArray);

        System.out.println("初始堆结构: " + minHeap);

        // 插入新元素
        System.out.println("插入元素6: " + minHeap.offer(6));
        System.out.println("插入元素0: " + minHeap.offer(0));
        System.out.println("插入后的堆结构: " + minHeap);

        // 获取最小值
        System.out.println("当前堆顶(最小值): " + minHeap.peek());

        // 替换堆顶元素
        minHeap.replace(7);
        System.out.println("替换堆顶元素后的堆结构: " + minHeap);

        // 更新指定索引的元素
        minHeap.update(3, 0);
        System.out.println("更新索引3为0后的堆结构: " + minHeap);

        // 取出堆顶元素
        System.out.println("取出的最小值: " + minHeap.poll());
        System.out.println("取出最小值后的堆结构: " + minHeap);

        // 检查堆是否已满
        System.out.println("堆是否已满: " + minHeap.isFull());

        // 继续插入元素，测试堆满的情况
        System.out.println("插入元素5: " + minHeap.offer(5));
        System.out.println("最终堆结构: " + minHeap);
    }




}
